// 题目：
//      把8个同样的球放在同样的5个袋子里，允许有的袋子空着不放，问共有多少种不同的法？
// 提示：如果8个球都放在一个袋子里，无论是放哪个袋子，都只算同一种分法。
// 解析：
//      把问题合成，先思索5个袋子都不空的状况，再思索4个袋子不空的状况，以此类推，最思索只运用一个袋子的状况（这种分法只要1种）
//      把一切子状况的分法数相加求出总分法。
//      进一步剖析，运用k个袋子装n个球（袋子不空），一共有几种分法的问题能够转化为k个数相加等于n的种数问题。
// 运用5个袋子装8个球则有3种：
//      1+1+1+1+4 = 8
//      1+1+1+2+3 = 8
//      1+1+2+2+2 = 8
// 运用4个袋子分8个球则有5种：
//      1+1+1+5=8
//      1+1+2+4=8
//      1+1+3+3=8
//      1+2+2+3=8
//      2+2+2+2=8
// 运用3个袋子分8个球则有5种：
//       1+1+6=8
//       1+2+5=8
//       1+3+4=8
//       2+2+4=8
//       2+3+3=8
// 运用2个袋子分8个球则有4种：
//      1+7=8
//      2+6=8
//      3+5=8
//      4+4=8
// 运用1个袋子装8个球则有1种：
//      8=8
// 因而，该问题的答案即为一切子状况下的和，3+5+5+4+1 = 18。

// 我们将这个问题一般化，并用程序来实现它。
//  将整数 N 分解成 K 个不为0的数之和，表示为f(N,K),
//  则上述问题转化为f(8,1)+f(8,2)+f(8,3)+f(8,4)+f(8,5)
// 我们可以通过动态规划来求解，终止条件很容易想到，关键是找到递推公式。
//
// 终止条件：
//      f(n, k) = 1, 当 k == 1 或 n == k;（很明显，只要一个袋子，或者袋子数和球数相同时只要一种分法） 
//      f(n, k) = 0, 当 n < k；（球数比袋子数少，则必然存在尚未应用的袋子，无解）
//
// 递推公式：
//      f(n, k) = f(n-1, k-1) + f(n-k, k)
//   如何理解？我们把分解的加数从小到大排列，第一个数要么是1，要么大于1，这样就可以分为这两种情况，将问题化小
//   【1】f(n-1, k-1）就是把第 1 个数放成 1，然后把剩下的 n-1 这个数分红 k-1 份。
//       f(n-1, k-1）就是原n，k问题中第一个数是 1 的一切分的办法数；
//   【2】f(n-k, k) 就是原n，k问题中第一个数不是 1（大于1），能够分的办法数。
//        这是一个关键点。认真剖析，相当于给 k 个位置，每个位置先放一个
//        1，（相当于每个袋子都有1个球）。 接下来剩下的 n-k ，这个数字再往这 k
//        个位置上分，这能够保证第一个位置至少比1大（第一个袋子的球数大于1）。
//    有了递推公式，这个问题就变得很简单了。

#include <iostream>
using namespace std;

int f(int N, int K) {
  if (K == 1 || N == K) return 1;
  if (N < K) return 0;

  return f(N - 1, K - 1) + f(N - K, K);
}

int main(int argc, char** argv) {
  int sum = 0;
  for (int i = 1; i <= 5; i++) {
    sum += f(8, i);
  }
  cout << "8个球放5个袋子, 所有方法数为：" << sum << endl;
  return 0;
}